import java.util.Vector;


public class VectorHeap<E> {
	protected Vector<E> data; // the data, kept in heap order
	public VectorHeap()
	// post: constructs a new priority queue
	{
	data = new Vector<E>();
	}
	
	public VectorHeap(Vector<E> v)
	// post: constructs a new priority queue from an unordered vector
	{
	int i;
	data = new Vector<E>(v.size()); // we know ultimate size
	for (i = 0; i < v.size(); i++)
	{ // add elements to heap
	add(v.get(i));
	}
	}
	
	/*
	public void add(E value)
	// pre: value is non-null
	// post: inserts value, leaves vector in order
	{
	int position = locate(value);
	data.add(position,value);
	}*/
	
	@SuppressWarnings("unchecked")
	protected int locate(E target)
	{
	Comparable<E> midValue;
	int low = 0; // lowest possible location
	int high = data.size(); // highest possible location
	int mid = (low + high)/2; // low <= mid <= high
	// mid == high iff low == high
	while (low < high) {
	// get median value
	midValue = (Comparable<E>) data.get(mid);
	// determine on which side median resides:
	if (midValue.compareTo(target) < 0) {
	low = mid+1;
	} else {
	high = mid;
	}
	// low <= high
	// recompute median index
	mid = (low+high)/2;
	}
	return low;
	}
	
	protected static int parent(int i)
	// pre: 0 <= i < size
	// post: returns parent of node at location i
	{
	return (i-1)/2;
	}
	
	protected static int left(int i)
	// pre: 0 <= i < size
	// post: returns index of left child of node at location i
	{
	return 2*i+1;
	}
	
	protected static int right(int i)
	// pre: 0 <= i < size
	// post: returns index of right child of node at location i
	{
	return 2*(i+1);
	}
	
	@SuppressWarnings("unchecked")
	protected void percolateUp(int leaf)
	// pre: 0 <= leaf < size
	// post: moves node at index leaf up to appropriate position
	{
	int parent = parent(leaf);
	E value = data.get(leaf);
	while (leaf > 0 &&
	(((Comparable<E>) value).compareTo(data.get(parent)) < 0))
	{
	data.set(leaf,data.get(parent));
	leaf = parent;
	parent = parent(leaf);
	}
	data.set(leaf,value);
	}
	
	public void add(E value)
	// pre: value is non-null comparable
	// post: value is added to priority queue
	{
	data.add(value);
	percolateUp(data.size()-1);
	}
}
